package main.Q101_200;

import java.util.*;

public class Q131_140 {
    public static void main(String[] args) {
        System.out.println("Question131：分割回文串");
        System.out.println("Question132：分割回文串 II");
        System.out.println("Question133：");
        System.out.println("Question134：加油站");
        System.out.println("Question135：分发糖果");
        System.out.println("Question136：只出现一次的数字");
        System.out.println("Question137：只出现一次的数字Ⅱ");
        System.out.println("Question138：复制带随机指针的链表");
        System.out.println("Question139：单词拆分");
        System.out.println("Question140：单词拆分Ⅱ");
    }
}

class Question131{
    List<List<String>> list=new ArrayList<>();
    public boolean isValid(String s){//判断是否为回文串
        char[] str=s.toCharArray();
        int left=0,right= str.length-1;
        while (left<=right){
            if (str[left]!=str[right]) return false;
            left++;
            right--;
        }
        return true;
    }
    public void process(int start,String s,List<String> lastList){
        if (start>s.length()-1){//所有字符均被分割
            List<String> tempList=new ArrayList<>();
            tempList.addAll(lastList);
            list.add(tempList);
            return;
        }
        for (int len=1;start+len<=s.length();len++){
            String temp=s.substring(start,start+len);
            if (isValid(temp)){//被分割的字符串为回文串
                lastList.add(temp);
                process(len+start,s,lastList);
                lastList.remove(lastList.size()-1);//撤销加入的回文串
            }
        }
    }
    public List<List<String>> partition(String s) {
        List<String> tempList=new ArrayList<>();
        process(0,s,tempList);
        return list;
    }
}

class Question132{
    public int minCut(String s) {
        int length=s.length();
        boolean[][] flag=new boolean[length][length];
        for (boolean[] cur:flag) Arrays.fill(cur,true);
        for (int i=length-1;i>=0;i--){
            for (int j=i+1;j<length;j++){
                flag[i][j]=s.charAt(i)==s.charAt(j)&&flag[i+1][j-1];
            }
        }
        int[] dp=new int[length];
        Arrays.fill(dp,Integer.MAX_VALUE);
        for (int i=0;i<length;i++){
            if (flag[0][i]) dp[i]=0;
            else {
                for (int j=0;j<i;j++){
                    if (flag[j+1][i]) dp[i]=Math.min(dp[i],dp[j]+1);
                }
            }
        }
        return dp[length-1];
    }
}

class Question134{
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int i = 0;
        while (i < n) {
            int sumOfGas = 0, sumOfCost = 0;
            int cnt = 0;
            while (cnt < n) {
                int j = (i + cnt) % n;
                sumOfGas += gas[j];
                sumOfCost += cost[j];
                if (sumOfCost > sumOfGas) {
                    break;
                }
                cnt++;
            }
            if (cnt == n) {
                return i;
            } else {
                i = i + cnt + 1;
            }
        }
        return -1;
//        int[] merge=new int[gas.length+cost.length];
//        int index=-1;
//        for (int i=0;i<merge.length/2;i++){
//            merge[2*i]=gas[i];
//            merge[2*i+1]=-1*cost[i];
//        }
//        boolean flag=true;
//        for (int i=0;i< merge.length;){
//            int total=0,start=i;
//            do{
//                total+=merge[start];
//                start=(start+1)% merge.length;
//                if (total<0){//此起点不能
//                    flag=false;
//                    break;
//                }else flag=true;
//            }while (start!=i);
//            if (flag) {
//                index=start;
//                break;
//            }
//            i+=2;
//        }
//        if (index==-1) return index;
//        else return index/2;
    }
}

class Question135{
    public int candy(int[] ratings) {
        int total=0;
        int[] dp=new int[ratings.length];
        Arrays.fill(dp,1);//初始都为1
        for (int i=1;i< ratings.length;i++) {
            if (ratings[i] > ratings[i-1]) dp[i]=dp[i-1]+1;
        }
        for (int i= ratings.length-1;i>0;i--) {
            if (ratings[i-1]>ratings[i]) dp[i-1]=Math.max(dp[i-1],dp[i]+1 );//左侧大于右侧，左侧+1
        }
        for (int i=0;i< ratings.length;i++) {
            total+=dp[i];
        }
        return total;
    }
}

class Question136{
    public int singleNumber(int[] nums) {
        int result=0;
        if (nums.length>2) {
            result=nums[0]^nums[1];
            for (int i = 2; i < nums.length; i++) {
                result = result ^ nums[i];
            }
        }else result=nums[0];
        return result;
    }
}

class Question137{
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int total = 0;
            for (int num: nums) {
                total += ((num >> i) & 1);
            }
            if (total % 3 != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }
}

class Question138{
    class Node {
        int val;
        Node next;
        Node random;
        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node copyRandomList(Node head) {
        if(head==null) return null;
        Map<Node,Node> map = new HashMap<Node,Node>();//创建一个哈希表，key是原节点，value是新节点
        Node p = head;
        while(p!=null) {//将原节点和新节点放入哈希表中
            Node newNode = new Node(p.val);
            map.put(p,newNode);
            p = p.next;
        }
        p = head;
        while(p!=null) {//遍历原链表，设置新节点的next和random
            Node newNode = map.get(p);
            if(p.next!=null) {
                newNode.next = map.get(p.next);
            }
            if(p.random!=null) {
                newNode.random = map.get(p.random);
            }
            p = p.next;
        }
        return map.get(head);
    }
}

class Question139{
    public boolean process(String s,int start,Set<String> wordDict){//回溯
        if (start==s.length()) return true;
        char startChar=s.charAt(start);
        boolean flag=false;
        for (String str:wordDict){
            if (startChar==str.charAt(0)&&start+str.length()-1<s.length()){//首字母匹配且长度未越界，继续匹配
                if (str.equals(s.substring(start,start+str.length()))){//该段被匹配
                    flag=process(s,start+str.length(),wordDict);
                }
            }
            if (flag) return flag;
        }
        return flag;
    }
    public boolean wordBreak(String s, List<String> wordDict) {
        int length=s.length();
        boolean[] dp=new boolean[length+1];
        dp[0]=true;
        for (int i=1;i<=length;i++){
            for (int j=0;j<i;j++){
                if (dp[j]&&wordDict.contains(s.substring(j,i))) {
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[length];
    }
}

class Question140{
    List<String> result,dict;
    public void process(String s,List<String> wordDict,String lastStr,int start) {
        if (start>=s.length()) {//结束递归
            result.add(lastStr.substring(0,lastStr.length()-1));
            return;
        }
        for (String word:wordDict) {
            int len=word.length();
            if (start+len<=s.length()&&word.equals(s.substring(start,start+len))) {//截取单词相等
                process(s,wordDict,lastStr+word+" ",start+len);
            }
        }
    }
    public List<String> wordBreak(String s, List<String> wordDict) {
        result=new ArrayList<>();
        dict=wordDict;
        process(s,wordDict,"",0);
        return result;
    }
}